package main.剑指OfferⅠ;

public class Day8 {
    public static void main(String[] args) {
        System.out.println("剑指Offer10-Ⅰ.斐波那契数列");
        System.out.println("剑指Offer10-Ⅱ.青蛙跳台阶问题");
        System.out.println("剑指Offer63.股票的最大利润");
    }
}

class Offer10_Ⅰ{
    public int fib(int n) {
        int first=0,second=1,third=0,MOD=(int)1e9+7;
        if (n==0) return first;
        if (n==1) return second;
        for (int i=1;i<n;i++){
            third=(first+second)%MOD;
            first=second;
            second=third;
        }
        return third%((int)1e9+7);
    }
}

class Offer10_Ⅱ{
    public int numWays(int n) {
        int first=1,second=2,third=1,MOD=(int)1e9+7;
        if (n==1) return first;
        if (n==2) return second;
        for (int i=2;i<n;i++){
            third=(first+second)%MOD;
            first=second;
            second=third;
        }
        return third;
    }
}

class Offer63{
    public int maxProfit(int[] prices) {
        int max=0,min=Integer.MAX_VALUE;
        for (int i=0;i<prices.length;i++){
            min=Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }
}